package leecode

import (
	"sort"
)

func smallestFromLeaf(root *TreeNode) string {
	pathArr := make([]string, 0)
	var dfs func(node *TreeNode, path string)
	dfs = func(node *TreeNode, path string) {
		if node == nil {
			return
		}
		path += intToLetter(node.Val)
		if node.Left == nil && node.Right == nil {
			str := reverseStringR(path)
			pathArr = append(pathArr, str)
			return
		}
		dfs(node.Left, path)
		dfs(node.Right, path)
	}
	dfs(root, "")
	sort.Strings(pathArr)
	return pathArr[0]
}

func reverseStringR(s string) string {
	// 将字符串转换为rune切片
	chars := []rune(s)
	// 获取字符串长度
	n := len(chars)
	// 使用双指针法反转字符串
	for i, j := 0, n-1; i < j; i, j = i+1, j-1 {
		chars[i], chars[j] = chars[j], chars[i]
	}
	// 将rune切片转换回字符串并返回
	return string(chars)
}

func intToLetter(num int) string {
	return string('a' + num)
}
